package com.hc.testaudio.deletea.util.forurier;


import com.hc.testaudio.deletea.bean.json.Twiddle;
import com.yc.yclibx.comment.YcLog;
import com.yc.yclibx.comment.YcResources;


/**
 * 基2-fft 快速傅里叶变换
 */
public class FftUtil {
    private final static double PI_2 = (2 * Math.PI);//2π 设置成静态常量以减少运算量
    private static double[] TWIDDLE_FACTOR_REAL;
    private static double[] TWIDDLE_FACTOR_IMAGE;

    static {
        YcLog.e("获取json文件里的旋转因子");
        Twiddle data = YcResources.getAssetsJson("twiddle.json", Twiddle.class);
        int length = data.getImage().size();
        TWIDDLE_FACTOR_REAL = new double[length];
        TWIDDLE_FACTOR_IMAGE = new double[length];
        for (int i = 0; i < length; i++) {
            TWIDDLE_FACTOR_REAL[i] = data.getReal().get(i);
            TWIDDLE_FACTOR_IMAGE[i] = data.getImage().get(i);
        }
    }

    /**
     * 码位的倒位序（即奇偶分解）
     *
     * @param data 原始数据
     */
    public static int[] binaryReverse(int[] data, int length, int level) {
        int[] newData = new int[length];
        for (int i = 0; i < length; i++) {
            int index = 0;
            int temp = i;
            //二进制位反转，求出需要替换的下标
            for (int k = 0; k < level; k++) {
                index = (index << 1) | (temp & 1);
                temp >>= 1;
            }
            newData[i] = data[index];
        }
        return newData;
    }

    /**
     * 获取所需进行fft蝶形运算的数量级
     */
    public static double[] getFFt(int[] data) {
        int level = 0;//蝶形的节点数
        int dataSize = data.length;
        int length = 1;
        while ((dataSize >>= 1) > 0) {
            level++;
            length <<= 1;
        }
        int[] reverseData2 = binaryReverse(data, length, level);
        return fft(reverseData2, level, length);

//        int dataSize = data.length;
//        int level = (int) (Math.log(dataSize) / Math.log(2));//蝶形的节点数
//        byte[] reverseData2 = binaryReverse(data, dataSize, level);
//        return fft(reverseData2, level, dataSize);
    }


    /**
     * @param data   代表经过码位的倒位序处理后的数据（即奇偶分解）
     * @param level  节点（L级蝶形运算）
     * @param length 处理过后的长度为2^L（该值必须为2的次方）
     */
    public static double[] fft(int[] data, int level, int length) {
        //按时间抽取发FFT的信号流图可知，当N=2^L时，共有L级蝶形运算；
        // 每级都由N/2个蝶形运算组成，而每个蝶形有1次复乘、2次复加，因此每级运算都需N/2次复乘和N次复加
        double[] resultReal = new double[length];
        double[] resultImage = new double[length];
        double[] tempResultReal = new double[length];
        double[] tempResultImage = new double[length];
        for (int k = 0; k < length; k++) {
            resultReal[k] = data[k];
            resultImage[k] = 0;
        }
        int distance = 2;//两个节点的距离 2^i
        int twiddleLength;
        int index2;
        int twiddleSum = TWIDDLE_FACTOR_REAL.length * 2;
        for (int i = 0; i < level; i++) {//共需要进行node次蝶形计算
            twiddleLength = distance >> 1;//旋转因子长度
            for (int k = 0; k < length; k++) {
                tempResultReal[k] = resultReal[k];
                tempResultImage[k] = resultImage[k];
            }
//            for (int k = 0; k < length / distance; k++) {     //蝶形运算：每一轮蝶形运算，都有n/2对的蝴蝶参与；n/2分为n/divBy组，每组divBy/2个。
//                int wIndex = 0;       //旋转因子下标索引
//                for (int j = k * distance; j < k * distance + distance / 2; j++) {
//                    index2 = j + twiddleLength;
//                    double X1 = tempResultReal[index2] * tempResultReal[wIndex] - tempResultImage[index2] * tempResultImage[wIndex];
//                    double X2 = tempResultImage[index2] * twiddleFactorReal[wIndex] + tempResultReal[index2] * twiddleFactorImage[wIndex];
//                    resultReal[j] = tempResultReal[j] + X1;
//                    resultImage[j] = tempResultImage[j] + X2;
//                    resultReal[index2] = tempResultReal[j] - X1; //蝶形对两成员距离相差divBy/2
//                    resultImage[index2] = tempResultImage[j] - X2;
//                    wIndex++;
//                }
//            }
            for (int j = 0; j < length; j++) {
                int distanceIndex = j % distance;
                int twiddleIndex = (distanceIndex % twiddleLength) * twiddleSum / distance;//对表
                if (distanceIndex < twiddleLength) {
                    index2 = j + twiddleLength;
                    resultReal[j] = tempResultReal[j] + tempResultReal[index2] * TWIDDLE_FACTOR_REAL[twiddleIndex] - tempResultImage[index2] * TWIDDLE_FACTOR_IMAGE[twiddleIndex];
                    resultImage[j] = tempResultImage[j] + tempResultImage[index2] * TWIDDLE_FACTOR_REAL[twiddleIndex] + tempResultReal[index2] * TWIDDLE_FACTOR_IMAGE[twiddleIndex];
                } else {
                    index2 = j - twiddleLength;
                    resultReal[j] = tempResultReal[index2] - (tempResultReal[j] * TWIDDLE_FACTOR_REAL[twiddleIndex] - tempResultImage[j] * TWIDDLE_FACTOR_IMAGE[twiddleIndex]);
                    resultImage[j] = tempResultImage[index2] - (tempResultImage[j] * TWIDDLE_FACTOR_REAL[twiddleIndex] + tempResultReal[j] * TWIDDLE_FACTOR_IMAGE[twiddleIndex]);
                }
            }
//            for (int j = 0; j < length; j++) {
//                int distanceIndex = j % distance;
//                if (distanceIndex < twiddleLength) {
//                    index2 = j + twiddleLength;
//                    int twiddleIndex = distanceIndex % twiddleLength;
//                    resultReal[j] = tempResultReal[j] + tempResultReal[index2] * twiddleFactorReal[twiddleIndex] - tempResultImage[index2] * twiddleFactorImage[twiddleIndex];
//                    resultImage[j] = tempResultImage[j] + tempResultImage[index2] * twiddleFactorReal[twiddleIndex] + tempResultReal[index2] * twiddleFactorImage[twiddleIndex];
//                } else {
//                    index2 = j - twiddleLength;
//                    int twiddleIndex = distanceIndex % twiddleLength;
//                    resultReal[j] = tempResultReal[index2] - (tempResultReal[j] * twiddleFactorReal[twiddleIndex] - tempResultImage[j] * twiddleFactorImage[twiddleIndex]);
//                    resultImage[j] = tempResultImage[index2] - (tempResultImage[j] * twiddleFactorReal[twiddleIndex] + tempResultReal[j] * twiddleFactorImage[twiddleIndex]);
//                }
//            }

//            for (int k = 0; k < n / divBy; k++) {     //蝶形运算：每一轮蝶形运算，都有n/2对的蝴蝶参与；n/2分为n/divBy组，每组divBy/2个。
//                int wIndex = 0;       //旋转因子下标索引
//                for (int j = k * divBy; j < k * divBy + divBy / 2; j++) {
//                    double X1 = tempXr[j + divBy / 2] * Wr[wIndex] - tempXi[j + divBy / 2] * Wi[wIndex];
//                    double X2 = tempXi[j + divBy / 2] * Wr[wIndex] + tempXr[j + divBy / 2] * Wi[wIndex];
//                    Xr[j] = tempXr[j] + X1;
//                    Xi[j] = tempXi[j] + X2;
//                    Xr[j + divBy / 2] = tempXr[j] - X1; //蝶形对两成员距离相差divBy/2
//                    Xi[j + divBy / 2] = tempXi[j] - X2;
//                    wIndex++;
//                }
//            }
//            for (int k = 0; k < length; k++) {    //FFT结果显示
//                System.out.println(resultReal[k] + " + j " + resultImage[k]);
//            }
//            System.out.println(" 一轮蝶式完成 ");
            distance <<= 1;
        }
        double[] result = new double[length];//傅里叶变换只有前面一半数据有用
        result[0] = resultReal[0];          //DC直流分量 ；第一个数据没有虚部的
        result[1] = resultReal[length / 2]; //Nyquist 奈奎斯特频率；
        for (int i = 2; i < length; i += 2) {    //FFT结果显示
            result[i] = resultReal[i / 2];
            result[i + 1] = resultImage[i / 2];
//            result[i] = YcCalculator.roundOff(resultReal[i / 2], 2);
//            result[i + 1] = YcCalculator.roundOff(resultImage[i / 2], 2);
        }

//        for (int i = 0; i < length; i++) {    //FFT结果显示
//            System.out.println(YcCalculator.roundOff(resultReal[i], 2) + " + j " + YcCalculator.roundOff(resultImage[i], 2));
//        }
        return result;
    }


    public static void main(String[] args) {
//        byte[] data2 = new byte[1024 * 8];
//        for (int i = 0; i < data2.length; i++) {
//            data2[i] = (byte) (i % 127);
//        }
        int distance = (int) Math.pow(2, 14);
        int twiddleLength = distance >> 1;//旋转因子长度
        double[] twiddleFactorReal = new double[distance];
        double[] twiddleFactorImage = new double[distance];
        for (int j = 0; j < twiddleLength; j++) {
            double twiddleFactorAngle = PI_2 * j / distance;
            twiddleFactorReal[j] = Math.cos(twiddleFactorAngle);
            twiddleFactorImage[j] = -Math.sin(twiddleFactorAngle);
        }
        for (int j = 0; j < twiddleLength; j++) {
            System.out.print(twiddleFactorReal[j] + ",");
        }
//        System.out.println("____________________");
//        for (int j = 0; j < twiddleLength; j++) {
//            System.out.print(twiddleFactorImage[j] + ",");
//        }
//        byte[] data2 = new byte[]{-3, 70, 118, -15, -5, 120, 56, 113, 20, 109, 84, 59, 43, 20, -116, -82, -3, 70, 118, -15, -5, 120, 56, 113, 21, 109, 84, 59, 43, 20, -116, -82};
//        int[] data2 = new int[60];
//        for (int i = 0; i < 60; i++) {
//            data2[i] = YcRandom.getInt(-127, 127);
//            System.out.print(data2[i] + " ");
//        }
//        System.out.println("---------------------1---------------------");
////        float[] result = FdtUtil.fdt(data2);
//        System.out.println("---------------------2---------------------");
////        int length = data2.length;
//        double[] reverseData2 = getFFt(data2);
//        System.out.println("----------------------3--------------------");
//        for (int i = 0; i < reverseData2.length; i++) {
//            System.out.println(reverseData2[i]);
//        }
//        System.out.println(Math.log10(35.383614));
    }

}